package com.likeycy.my.tree;

import com.likeycy.my.printer.BinaryTreeInfo;

import java.util.*;

/**
 * @ClassName: BinaryTree
 * @Description: TODO
 * @Author: sodagreen
 * @Date: 2021/3/18 22:53
 * @Version: 1.0
 */
public class BinaryTree<E> implements BinaryTreeInfo {

    private final List<E> list = new ArrayList<>();

    /** 元素总数目 */
    protected int size;
    /** 根节点 */
    protected Node<E> root;

    /**
     * 内部接口
     * @param <E>
     */
    public static abstract class Visitor<E> {
        boolean stop;

        /**
         * 遍历时候控制方法
         * @param element 遍历树时取出的节点元素
         * @return 如果返回true，终止遍历。如果返回false，继续遍历
         */
        protected abstract boolean visit(E element);
    }

    public void preorder(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        preorder(root, visitor);
    }

    private void preorder(Node<E> node, Visitor<E> visitor) {
        if (node == null) {
            return;
        }
        Stack<Node<E>> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            Node<E> cur = stack.pop();
            visitor.stop = visitor.visit(cur.element);
            if (visitor.stop) {
                return;
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

    public void inorder(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        inorder(root, visitor);
    }

    private void inorder(Node<E> node, Visitor<E> visitor) {
        if (node == null) {
            return;
        }
        Stack<Node<E>> stack = new Stack<>();
        Node<E> head = node;
        while (!stack.isEmpty() || head != null) {
            while (head != null) {
                stack.push(head);
                head = head.left;
            }
            Node<E> temp = stack.pop();
            visitor.stop = visitor.visit(temp.element);
            if (visitor.stop) {
                return;
            }
            head = temp.right;
        }
    }

    public void postorder(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        postorder(root, visitor);
    }

    private void postorder(Node<E> node, Visitor<E> visitor) {
        if (node == null) {
            return;
        }
        Deque<Node<E>> stack = new LinkedList<>();
        Node<E> prev = null;
        Node<E> head = node;
        while (!stack.isEmpty() || head != null) {
            while (head != null) {
                stack.push(head);
                head = head.left;
            }
            head = stack.pop();
            if (head.right == null || head.right == prev) {
                visitor.stop = visitor.visit(head.element);
                if (visitor.stop) {
                    return;
                }
                prev = head;
                head = null;
            } else {
                stack.push(head);
                head = head.right;
            }
        }
    }

    public void levelOrder(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        levelOrder(root, visitor);
    }

    private void levelOrder(Node<E> node, Visitor<E> visitor) {
        if (root == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            Node<E> cur = queue.poll();
            // 提供一个钩子函数，让外部决定如何处理这些元素
            visitor.stop = visitor.visit(cur.element);
            if (visitor.stop) {
                return;
            }
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    /**
     * 静态的内部类，作为存放节点的数据
     * @param <E>
     */
    public static class Node<E> {
        /** 存储节点数据 */
        E element;
        /** 左边节点 */
        Node<E> left;
        /** 右边节点 */
        Node<E> right;
        /** 父节点，如果该节点为空，表示当前Node为根节点 */
        Node<E> parent;
        public Node(E element, Node<E> left, Node<E> right, Node<E> parent) {
            this.element = element;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        /**
         * 判断是否为叶子节点
         * @return
         */
        public boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 判断当前节点下的左右子节点不为空
         * @return
         */
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        /**
         * 判断当前节点(自己)是否为父节点的左子节点
         * @return 返回true表示是左子节点，false反之
         */
        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        /**
         * 判断当前节点(自己)是否为父节点的右子节点
         * @return 返回true表示是右子节点，false反之
         */
        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }
    }

    /**
     * 获取元素的总数目
     * @return
     */
    public int size() {
        return size;
    }


    /**
     * 判断存储元素的容器是否为空
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 清空存储元素的容器
     */
    public void clear() {
        root = null;
        size = 0;
    }

    /**
     * 前序遍历二叉树，访问顺序：根节点、前序遍历左子树、前序遍历右子树
     * @return 返回遍历后的list集合
     */
    public List<E> preorderTraversal() {
        // 递归方式遍历
        /*List<E> list = preorderTraversalByRecursion(root);*/

        // 迭代方式遍历
        /*List<E> list = preorderTraversalByForeachInStack(root);*/

        // 迭代方式二：模板解法
        List<E> list = preorderTraversalByForInStack_2(root);
        return this.list;
    }

    /**
     * 前序遍历，递归方式
     * @param node 要遍历的node实例
     * @return 返回遍历后的list集合
     */
    private List<E> preorderTraversalByRecursion(Node<E> node) {
        if (node == null) {
            return list;
        }
        list.add(node.element);
        preorderTraversalByRecursion(node.left);
        preorderTraversalByRecursion(node.right);
        return list;
    }

    /**
     * 迭代方式前序遍历。前序遍历为根——左——右。通过用栈结构，将根节点入栈，循环时出栈取出根节点，
     * 然后将右子节点先入栈，再加左子节点入栈。这样下一轮循环的时候取出栈顶元素时会先取出左子节点，然后是右子节点，
     * 符合根——左——右的遍历顺序
     * @param node
     * @return
     */
    private List<E> preorderTraversalByForeachInStack(Node<E> node) {
        Stack<Node<E>> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            Node<E> currentNode = stack.pop();
            list.add(currentNode.element);
            if (currentNode.right != null) {
                stack.push(currentNode.right);
            }
            if (currentNode.left != null) {
                stack.push(currentNode.left);
            }
        }
        return list;
    }

    /**
     * 迭代模板解法，前序遍历。
     * 先将根节点 cur 和所有的左孩子入栈并加入结果中，直至 cur 为空，用一个 while 循环实现
     * 然后，每弹出一个栈顶元素 tmp，就到达它的右孩子，再将这个节点当作 cur 重新按上面的步骤来一遍，直至栈为空。
     * 这里又需要一个 while 循环
     * @param node
     * @return
     */
    private List<E> preorderTraversalByForInStack_2(Node<E> node) {
        Stack<Node<E>> stack = new Stack<>();
        Node<E> head = node;
        while (!stack.isEmpty() || head != null) {
            // 通过内部while循环，可以先将左子树的所有左子节点入栈。当来到左子树最左的叶子节点时，head为null了。
            // 此时会结束while循环，然后每取出一个栈顶的左子节点就会直接访问右子节点。
            while (head != null) {
                list.add(head.element);
                stack.push(head);
                head = head.left;
            }
            Node<E> tempNode = stack.pop();
            head = tempNode.right;
        }
        return list;
    }

    /**
     * 中序遍历。访问顺序：中序遍历左子树、根节点、中序遍历右子树
     * 中序遍历特点是所有元素都是按照自然顺序升序或者降序排列的
     * 比如遍历完成后是 1,2,3,4,5 或者是 5,4,3,2,1
     * @return 返回遍历后的list集合
     */
    public List<E> inorderTraversal() {
        // 中序遍历递归方式
//        List<E> list = inorderTraversalByRecursion(root);

        // 中序遍历迭代方式
        List<E> list = inorderTraversalByForInStack_2(root);
        return list;
    }

    /**
     * 中序遍历，递归方式。中序遍历特点是所有元素都是按照自然顺序升序或者降序排列
     * @param node 要遍历的node实例
     * @return 返回遍历后的list集合
     */
    private List<E> inorderTraversalByRecursion(Node<E> node) {
        if (node == null) {
            return list;
        }
        inorderTraversalByRecursion(node.left);
        list.add(node.element);
        inorderTraversalByRecursion(node.right);
        return list;
    }

    /**
     * 迭代模板解法，中序遍历。中序遍历和前序遍历的模板解法是一样的
     * 1.创建一个Stack，然后按 左 中 右的顺序输出节点。
     * 2.尽可能的将这个节点的左子树压入Stack，此时栈顶的元素是最左侧的元素，其目的是找到一个最小单位的子树
     *   (也就是最左侧的一个节点)，并且在寻找的过程中记录了来源，才能返回上层,同时在返回上层的时候已经处理完毕左子树了。
     * 3.当处理完最小单位的子树时，返回到上层处理了中间节点。（如果把整个左中右的遍历都理解成子树的话，就是处理完
     *   左子树->中间(就是一个节点)->右子树）
     * 4.如果有右节点，其也要进行中序遍历。
     * @param node
     * @return
     */
    private List<E> inorderTraversalByForInStack_2(Node<E> node) {
        Stack<Node<E>> stack = new Stack<>();
        Node<E> head = node;
        while (!stack.isEmpty() || head != null) {
            // 通过内部while循环，可以先将左子树的所有左子节点入栈。当来到左子树最左的叶子节点时，head为null了。
            // 此时会结束while循环，然后每取出一个栈顶的左子节点就会直接访问右子节点。
            while (head != null) {
                // 添加根节点
                stack.push(head);
                // 循环添加左节点
                head = head.left;
            }
            Node<E> tempNode = stack.pop();
            list.add(tempNode.element);
            head = tempNode.right;
        }
        return list;
    }



    /**
     * 后序遍历。访问顺序：后序遍历左子树、后序遍历右子树、根节点
     * @return 返回遍历后的list集合
     */
    public List<E> postorderTraversal() {
        // 后序遍历递归方式
//        List<E> list = postorderTraversalByRecursion(root);

        // 后序遍历迭代方式
//        List<E> list = postorderTraversalByForInDoubleStack(root);
//        List<E> list = postorderTraversalByForStackTemplate(root);

        List<E> list = postorderTraversalByCursor(root);
        return this.list;
    }

    /**
     * 后序遍历，递归方式
     * @param node 要遍历的node实例
     * @return 返回遍历后的list集合
     */
    private List<E> postorderTraversalByRecursion(Node<E> node) {
        if (node == null) {
            return list;
        }
        postorderTraversalByRecursion(node.left);
        postorderTraversalByRecursion(node.right);
        list.add(node.element);
        return list;
    }

    /**
     * 后序遍历。访问顺序是左——右——中。和前序遍历的中——左——右有些类似。不同的是根节点也就是中最后访问。
     * 可以使用前序遍历的思路，将其遍历顺序改为中——右——左。这样得到的结果再反转输出就会变成左——右——中。
     * 1.前序遍历的过程 是 中左右。
     * 2.将其转化成 中右左。也就是压栈的过程中优先压入左子树，在压入右子树。
     * 3.然后将这个结果返回来，这里是利用栈的先进后出倒序打印。
     * @param node
     * @return
     */
    private List<E> postorderTraversalByForInDoubleStack(Node<E> node) {
        Stack<Node<E>> stack1 = new Stack<>();
        Stack<Node<E>> stack2 = new Stack<>();
        stack1.push(node);
        while (!stack1.isEmpty()) {
            Node<E> cur = stack1.pop();
            stack2.push(cur);
            if (cur.left != null) {
                stack1.push(cur.left);
            }
            if (cur.right != null) {
                stack1.push(cur.right);
            }
        }

        while (!stack2.isEmpty()) {
            list.add(stack2.pop().element);
        }
        return list;
    }

    /**
     * 后序遍历，模板解法
     * @param node
     * @return
     */
    private List<E> postorderTraversalByForStackTemplate(Node<E> node) {
        Node<E> cur = node;
        Stack<Node<E>> stack = new Stack<>();
        List<E> res = new ArrayList<>();
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                res.add(cur.element);
                stack.push(cur);
                cur = cur.right;
            }
            Node<E> temp = stack.pop();
            cur = temp.left;
        }

        int size = res.size();
        for (int i = size-1; i >= 0; i--) {
            list.add(res.get(i));
        }
        return list;
    }

    /**
     * 后序遍历。leetode官方解法
     * @param node
     * @return
     */
    private List<E> postorderTraversalByCursor(Node<E> node) {
        Deque<Node<E>> stack = new LinkedList<>();
        Node<E> prev = null;
        Node<E> head = node;
        while (!stack.isEmpty() || head != null) {
            while (head != null) {
                stack.push(head);
                head = head.left;
            }
            head = stack.pop();
            if (head.right == null || head.right == prev) {
                list.add(head.element);
                prev = head;
                head = null;
            } else {
                stack.push(head);
                head = head.right;
            }
        }
        return list;
    }

    /**
     * 层序遍历，访问顺序：从上到下、从左到右依次访问每一个节点
     * @return
     */
    public List<E> levelOrderTraversal() {
        // 使用队列进行二叉树层序遍历
        List<E> list = levelOrderTraversalByQueue(root);
        return list;
    }

    /**
     * 层序遍历。使用对队列实现
     * 通过将根节点入队，循环的将左右子节点入队。然后取出头节点，
     * 先入队当前头节点的左子节点，然后入队当前节点的右子节点，一直循环到每个叶子节点
     * 然后判断队列是否为空，为空表示遍历完了
     * @param node
     * @return
     */
    private List<E> levelOrderTraversalByQueue(Node<E> node) {
        // 声明一个队列，用来将节点入队存储
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(node);

        while (!queue.isEmpty()) {
            Node<E> currentNode = queue.poll();
            list.add(currentNode.element);
            if (currentNode.left != null) {
                queue.offer(currentNode.left);
            }

            if (currentNode.right != null) {
                queue.offer(currentNode.right);
            }
        }

        return list;
    }

    /**
     * 计算二叉树的高度
     * @return
     */
    public int height() {
        return heightByForLevelOrder(root);
    }

    /**
     * 递归实现计算二叉树的高度
     * @param node
     * @return
     */
    private int heightByRecursion(Node<E> node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(heightByRecursion(node.left), heightByRecursion(node.right));
    }

    /**
     * 层序遍历实现计算二叉树的高度
     * @param node
     * @return
     */
    private int heightByForLevelOrder(Node<E> node) {
        if (node == null) {
            return 0;
        }
        // 树的高度
        int height = 0;
        // 存储的每一层节点数的长度,根节点是从1开始
        int levelNodeSize = 1;
        Queue<Node<E>> stack = new LinkedList<>();
        stack.offer(node);
        while (!stack.isEmpty()) {
            Node<E> cur = stack.poll();
            // 每遍历一层取出该层的一个节点时，长度就需要减少
            levelNodeSize--;
            if (cur.left != null) {
                stack.offer(cur);
            }

            if (cur.right != null) {
                stack.offer(cur.right);
            }

            // 如果当前的长度等于0，表示已经遍历完一整层了。那么剩下的就是下一层的节点总数
            if (levelNodeSize == 0) {
                // 下一层的节点总数
                levelNodeSize = stack.size();
                // 高度加1
                height++;
            }
        }
        return 0;
    }

    /**
     * 提供一个创建新Node的实例的方法，供不同子类进行不同的实现
     * @param element 要添加的指定元素
     * @param parent 新增节点的父节点
     * @return 返回新增的节点对象
     */
    protected Node<E> newNode(E element, Node<E> parent) {
        return new Node<>(element,parent);
    }


    /**
     * 实现一：判断一棵树是否为完全二叉树
     * 1.判断树是否为空，不为空开始层序遍历二叉树（用队列）
     * 2.如果 node.left != null && node.right != null ，将 node.left和 node.right按顺序入队
     * 3.如果 node.left == null && node.right != null ，返回false
     * 4.如果 node.left != null && node.right == null ，或者 node.left == null && node.right == null
     * 那么后面遍历的节点应该都是叶子节点，才是完全二叉树。否则返回false
     * @return 返回true表示是全完二叉树，返回false表示不是
     */
    public boolean isCompleteBinaryTree () {
        if (root == null) {
            return false;
        }
        Queue<Node<E>> stack = new LinkedList<>();
        Node<E> head = root;
        stack.offer(head);
        boolean leaf = false;
        while (!stack.isEmpty()) {
            Node<E> node = stack.poll();
            if (leaf && !node.isLeaf()) {
                return false;
            }
            if (node.left != null && node.right != null) {
                stack.offer(node.left);
                stack.offer(node.right);
            } else if (node.left == null && node.right != null) {
                return false;
            } else {
                // 遍历到此处是，该节点必然是叶子节点
                leaf = true;
                if (node.left != null) {
                    stack.offer(node.left);
                }
            }
        }
        return true;
    }

    /**
     * 实现二：判断一棵树是否完全二叉树
     * @return
     */
    public boolean isCompleteBinary2() {
        if (root == null) {
            return false;
        }
        Queue<Node<E>> stack = new LinkedList<>();
        Node<E> head = root;
        stack.offer(head);
        boolean leaf = false;
        while (!stack.isEmpty()) {
            Node<E> node = stack.poll();
            if (leaf && !node.isLeaf()) {
                return false;
            }

            if (node.left != null) {
                stack.offer(node.left);
            } else if (node.right != null) {
                return false;
            }

            if (node.right != null) {
                stack.offer(node.right);
            } else {
                leaf = true;
            }
        }
        return true;
    }

    /**
     * 在二叉树中查找指定节点的前驱节点
     * @param node 指定的节点
     * @return 返回查找到的前驱节点，如果没有找到返回null
     */
    protected Node<E> predecessor(Node<E> node) {
        if (node == null) {
            return null;
        }
        Node<E> p = node.left;
        // 前驱节点在左子树中当中，一直right
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }

        // 从父节点、祖父节点中寻找前驱节点
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        /*
         * 退出循环执行到此处时，会有两种情况。
         * 一种是：node.parent == null。这种情况一直往上找父节点找不到了，那说明没有前驱。那么返回
         *        node.parent就相当于返回null
         * 一种是：node == node.parent.right。这种情况发现节点在子树中是父节点的右孩子节点，
         *        那么右孩子节点的parent就是当前node的前驱节点。
         */
        return node.parent;
    }

    /**
     * 在二叉树中查找指定节点的后继节点
     * @param node 指定的节点
     * @return 返回查找到的后继节点，返回null表示指定节点没有后继节点
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) {
            return null;
        }
        Node<E> s = node.right;
        // 后继节点在右子树中当中，一直left
        if(s != null) {
            while (s.left != null) {
                s = s.left;
            }
            return s;
        }

        while (node.parent == null && node == node.parent.right) {
            node = node.parent;
        }

        return node.parent;
    }


    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> currentNode = (Node<E>) node;
        String parentElementStr = "null";
        if (currentNode.parent != null) {
            parentElementStr = currentNode.parent.element.toString();
        }
        return currentNode.element + "_p[" + parentElementStr + "]";
    }
}
